package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.jar.JarEntry;

/**
 * 三数之和
 * 15
 */
@SuppressWarnings("all")
public class ThreeSum{
    public static void main(String[] args) {
        Solution solution = new ThreeSum().new Solution();
        /**
         * 1.暴力求解 --三重for循环
         * 2.哈希表保存结果
         * 3.左右双指针-->三指针
         */
        int[] ints = {-1, 0, 1, 2, -1, -4};
        solution.threeSum(ints);
    }

    /**
     * 双指针加排序的方式--->三指针法
     * 三数之和等于0
     * 一个数去找另外的两个数
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //时间复杂度--logn
        Arrays.sort(nums);
        //遍历每一个元素,最小的那个元素作为核心
        //时间复杂度--n*n
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0)
                break;
            //相同的数跳过
            if (i>0&&nums[i-1]==nums[i])
                continue;
            //以当前数作为核心,定义左右指针
            int left=i+1,right=nums.length-1;
            while (left<right) {
                int sum =nums[i] + nums[left] +nums[right];
                if (sum==0) {
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    //如果移动之后的元素相同,直接跳过-->若重叠多个的话,while可以跳过多个.
                    while (left<right&&nums[--left]==nums[left]) left++;
                    while (left<right&&nums[right]==nums[++right]) right--;
                }
               if (sum<0) {
                   //小于0的话,较小的数增大
                   left++;
               }
               if (sum>0) {
                   //大于0的话,较大的数减小
                   right--;
               }
            }
        }
        return list;
    }
    /**
     * 哈希表保存结果方法
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        //保存临时结果
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        //保存结果集
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = 0 - nums[i];
            if (map.containsKey(temp)) {
                //这个时候map里面包含了这个数,意味着找到这个数
                ArrayList<Integer> integers = new ArrayList<>(map.get(temp));
                integers.add(nums[i]);
                list.add(integers);
            }
            for (int j =i+1; j < nums.length; j++) {
                int twoTemp = nums[i] + nums[j];
                //如果Key不存在
                if (!map.containsKey(twoTemp)) {
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.add(nums[i]);
                    integers.add(nums[j]);
                    map.put(twoTemp,integers);
                }
                //如果key存在---比较复杂

            }

        }
        return list;
    }

class Solution {
    //暴力法
    public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    int temp = nums[i] + nums[j] + nums[k];
                    if (temp==0) {
                        ArrayList<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]);
                        integers.add(nums[j]);
                        integers.add(nums[k]);
                        list.add(integers);
                    }
                }
            }
        }
        List<List<Integer>> duplicateList = duplicate(list);
        return duplicateList;
    }

    /**
     * 暴力法去重
     * @param list
     * @return
     */
    public List<List<Integer>> duplicate(List<List<Integer>> list) {
        //List元组去重
        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                ArrayList<Integer> listI = (ArrayList<Integer>) list.get(i);
                boolean flag = duplicateList(listI, (ArrayList<Integer>) list.get(j));
                if (flag) {
                    list.remove(j);
                    continue;
                }
            }
        }
        return list;
    }

    /**
     * 暴力法去重一个三元组
     loop     * @param listI
     * @param listJ
     * @return
     */
    public boolean duplicateList(ArrayList<Integer> listI,ArrayList<Integer> listJ) {
        for (int i = 0; i < listI.size(); i++) {
            for (int j = 0; j < listJ.size(); j++) {

            }
        }
        //等于0  表示两个list相等
        return listJ.size()==0;
    }
}

}